home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / glimpse-2.1 / index / region.c < prev    next >
C/C++ Source or Header  |  1995-05-16  |  13KB  |  567 lines

  1. /* Copyright (c) 1994 Sun Wu, Udi Manber, Burra Gopal.  All Rights Reserved. */
  2. /* From mail received from Bill Camargo and Darren Hardy in June 1994 */
  3. #include <stdio.h>
  4. #include "region.h"
  5.  
  6. /*
  7.  * Exports the following routines. Any filtering/attr-val parsing mechanism
  8.  * can be integrated into glimpse and glimpseindex with this interface.
  9.  */
  10.  
  11. char * /* attrname = */ attr_id_to_name(/* int attrid */);
  12. int /* attrid = */ attr_name_to_id(/* char *attrname */);
  13. int attr_dump_names(/* char *filename */);
  14. int attr_load_names(/* char *filename */);
  15. int attr_free_table(/* void */);
  16. int region_initialize(/* void */);
  17. int region_destroy(/* void */);
  18. int region_create(/* char *filename */);
  19. int /* attrid = */ region_identify(/* int offset_in_file, int len_of_region */);
  20.  
  21. #if    STRUCTURED_QUERIES
  22.  
  23. printsp()
  24. {
  25.     int    x;
  26.  
  27.     printf("stack at %x\n", &x);
  28. }
  29.  
  30. /*****************************************************************************/
  31.  
  32. #define ATTR_HASH_TABLE_SIZE    256    /* must be a power of 16=multiple of 4 bits */
  33. #define ATTR_HASH_TABLE_MASK    0xff    /* bits that mask off the bits in TABLE_SIZE */
  34. #define ATTR_HASH_STEP_SIZE    2    /* #of nibbles that make up TABLE_SIZE */
  35.  
  36. attr_element_t    *attr_hash_table[ATTR_HASH_TABLE_SIZE];
  37. char    **attr_name_table = NULL;
  38. int    attr_num = 0;
  39. int    attr_maxid = 0;
  40.  
  41. /* English language characters have all info in lowest 4 bits */
  42. int
  43. attr_hash_index(word, len)
  44.     char    *word;
  45.     int    len;
  46. {
  47.     int    i=0, j, index = 0, temp;
  48.  
  49.     for (i=0; i+ATTR_HASH_STEP_SIZE<=len; i+=ATTR_HASH_STEP_SIZE) {
  50.         temp = 0;
  51.         for (j=0; j<ATTR_HASH_STEP_SIZE; j++)
  52.             temp = (temp << 4) | word[i+j] & 0x0f;
  53.         index = (index + temp) & ATTR_HASH_TABLE_MASK;
  54.     }
  55.     temp = 0;
  56.     for (j=0; i+j<len; j++)
  57.         temp = (temp << 4) | word[i+j] & 0x0f;
  58.     index = (index + temp) & ATTR_HASH_TABLE_MASK;
  59.     return index;
  60. }
  61.  
  62. char *
  63. attr_id_to_name(id)
  64.     int    id;
  65. {
  66. #if    0
  67.     printf("id = %d\n", id);
  68. #endif    /*0*/
  69.     if ((attr_name_table == NULL) || (id > attr_maxid)) return NULL;
  70.     else return attr_name_table[id];
  71. }
  72.  
  73. /*
  74.  * returns the attribute number associated with name, 0 for no attribute --
  75.  * NOTE: name may not be null terminated and you are not allowed to alter it.
  76.  * called during indexing and search.
  77.  */
  78. int
  79. attr_name_to_id(name, len)
  80.     char    *name;
  81.     int    len;
  82. {
  83.     int        index = attr_hash_index(name, len);
  84.     attr_element_t    *e = attr_hash_table[index];
  85. #if    0
  86.     char        c = name[len];
  87.     name[len] = '\0';
  88.     fprintf(stderr, "attr=%s @ %d?\n", name, index);
  89.     fflush(stderr);
  90.     name[len] = c;
  91. #endif    /*0*/
  92.  
  93.     while(e != NULL) {
  94.         if (!strncmp(e->attribute, name, len)) break;
  95.         else e = e->next;
  96.     }
  97.     if (e!=NULL) {
  98. #if    0
  99.         fprintf(stderr, "foundid=%d\n", e->attributeid);
  100. #endif    /*0*/
  101.         return e->attributeid;
  102.     }
  103.     return 0;
  104. }
  105.  
  106. /*
  107.  * returns the attribute number (> 0) for the attribute "name". It adds the
  108.  * name as a newly seen attribute if it doesn't exist already (using #tables).
  109.  * called in region_create, which is called during indexing.
  110.  */
  111. attr_insert_name(name, len)
  112.     char    *name;
  113.     int    len;
  114. {
  115.     int        index = attr_hash_index(name, len);
  116.     attr_element_t    **pe = &attr_hash_table[index], *e;
  117.  
  118.     while(*pe != NULL) {
  119.         if (!strcmp((*pe)->attribute, name)) break;
  120.         else pe = &(*pe)->next;
  121.     }
  122.     if (*pe!=NULL) return (*pe)->attributeid;
  123.  
  124.     e = (attr_element_t *)my_malloc(sizeof(attr_element_t));
  125.     e->attribute = (char *)my_malloc(len + 2);
  126.     strncpy(e->attribute, name, len + 1);
  127.     e->attributeid = (++attr_num);
  128.     e->next = NULL;
  129.     *pe = e;
  130. #if    0
  131.     fprintf(stderr, "inserting %s %d\n", name, attr_num);
  132. #endif    /*0*/
  133.     return e->attributeid;
  134. }
  135.  
  136. /*
  137.  * frees current hash table of attr-value pairs.
  138.  * called after dump in indexing, and at end of search (after previous load).
  139.  */
  140. int
  141. attr_free_table()
  142. {
  143.     int    i;
  144.     attr_element_t *e, *temp;
  145.  
  146.     for (i=0; i<ATTR_HASH_TABLE_SIZE; i++) {
  147.         e = attr_hash_table[i];
  148.         while (e != NULL) {
  149.             temp = e->next;
  150. #if    BG_DEBUG
  151.             memory_usage -= strlen(e->attribute) + 2;
  152. #endif    /*BG_DEBUG*/
  153.             my_free(e->attribute, 0);
  154.             my_free(e, sizeof(attr_element_t));
  155.             e = temp;
  156.         }
  157.         attr_hash_table[i] = NULL;
  158.     }
  159.     if (attr_name_table != NULL) {
  160.         my_free(attr_name_table, sizeof(attr_element_t *) * ATTR_HASH_TABLE_SIZE);
  161.         attr_name_table = NULL;
  162.     }
  163.     return 0;
  164. }
  165.  
  166. /* Looks for embedded attributes and copies the real attribute into dest */
  167. attr_extract(dest, src)
  168.     char    *dest, *src;
  169. {
  170.     char    *oldsrc = src;
  171.  
  172. check_again:
  173.     if (!strncmp("embed<", src, 6) || !strncmp("Embed<", src, 6) || !strncmp("EMBED<", src, 6)) {
  174.         src += 6;
  175.         while ((*src != '>') && (*src != '\0')) src++;
  176.         if (*src == '\0') {
  177.             strcpy(dest, oldsrc);
  178.             return;
  179.         }
  180.         while (!isalnum(*src)) src ++;    /* assuming type names are .. */
  181.         oldsrc = src;
  182.         goto check_again;
  183.     }
  184.     strcpy(dest, src);
  185.     return;
  186. }
  187.  
  188. /*
  189.  * dumps the attribute-list into a file name (id, name, \n)
  190.  * into the file specified and then destroys the hash table.
  191.  * Returns #of attributes dumped into the file, -1 if error.
  192.  * called at the end of indexing.
  193.  */
  194. int
  195. attr_dump_names(filename)
  196.     char    *filename;
  197. {
  198.     int    i=0;
  199.     int    ret = -1;
  200.     FILE    *fp = fopen(filename, "w");
  201.     attr_element_t *e;
  202.  
  203. #if    0
  204.     printf("in dump attr\n");
  205. #endif    /*0*/
  206.     if (fp == NULL) return -1;
  207.     ret = 0;
  208.     for (i=0; i<ATTR_HASH_TABLE_SIZE; i++) {
  209.         e = attr_hash_table[i];
  210.         while (e != NULL) {
  211.             fprintf(fp, "%d,%s ", e->attributeid, e->attribute);
  212.             e = e->next;
  213.             ret ++;
  214.         }
  215.         fputc('\n', fp);
  216.     }
  217.     fflush(fp);
  218.     fclose(fp);
  219.     return ret;
  220. }
  221.  
  222. /*
  223.  * constructs a hash-table of attributes by reading them from the file.
  224.  * Returns #of attributes read from the file, -1 if error.
  225.  * Does not recompute hash-indices of attributes.
  226.  * called before searching for attr=val pairs.
  227.  */
  228. int
  229. attr_load_names(filename)
  230.     char    *filename;
  231. {
  232.     int    index = 0, ret = 0;
  233.     FILE    *fp = fopen(filename, "r");
  234.     attr_element_t *e;
  235.     int    c = 0;
  236.     char    temp[1024];    /* max attr name */
  237.     char    buffer[1024+32];/* max attr id pair */
  238.     int    i;
  239.     int    id;
  240.  
  241.     attr_maxid = 0;
  242.     memset(attr_hash_table, '\0', sizeof(attr_element_t *) * ATTR_HASH_TABLE_SIZE);
  243.     if (fp == NULL) return -1;
  244.     while ((c = getc(fp)) != EOF) {
  245.         if (c == '\n') {
  246.             index ++;
  247.             continue;
  248.         }
  249.         ungetc(c, fp);
  250.         /* fscanf screws up fp and skips over trailing space characters (\t,\n, ) */
  251.         i=0;
  252.         while ((c=getc(fp)) != ' ') buffer[i++] = c;
  253.         buffer[i] = '\0';
  254. #if    0
  255.         printf("buffer=%s\n", buffer);
  256. #endif    /*0*/
  257.         sscanf(buffer, "%d,%1023s", &id, temp);
  258.         temp[1023] = '\0';
  259. #if    0
  260.         printf("read attr=%s,%d @ %d\n", temp, id, index);
  261. #endif    /*0*/
  262.         if (id <= 0) continue;
  263.         e = (attr_element_t *)my_malloc(sizeof(attr_element_t));
  264.         e->attributeid = id;
  265.         if (id > attr_maxid) attr_maxid = id;
  266.         e->attribute = (char *)my_malloc(strlen(temp) + 2);
  267.         strcpy(e->attribute, temp);
  268.         e->next = attr_hash_table[index];
  269.         attr_hash_table[index] = e;
  270.         ret ++;
  271.         if (index >= ATTR_HASH_TABLE_SIZE - 1) break;
  272.     }
  273.     fclose(fp);
  274.  
  275.     attr_name_table = (char **)my_malloc(sizeof(char *) * (ret=(ret >= (attr_maxid + 1) ? ret : (attr_maxid + 1))));
  276.     memset(attr_name_table, '\0', sizeof(char *) * ret);
  277.     for (i=0; i<ATTR_HASH_TABLE_SIZE; i++) {
  278.         e = attr_hash_table[i];
  279.         while (e!=NULL) {
  280.             attr_name_table[e->attributeid] = e->attribute;
  281.             e = e->next;
  282.         }
  283.     }
  284.     return ret;
  285. }
  286.  
  287. /***************************************************************************/
  288.  
  289. region_t *current_regions, *nextpos;    /* nextpos is hint into list */
  290.  
  291. /*
  292.  * Called during indexing before region_create.
  293.  * returns 0.
  294.  */
  295. int
  296. region_initialize()
  297. {
  298.     attr_num = 0;
  299.     attr_name_table = NULL;
  300.     memset(attr_hash_table, '\0', sizeof(attr_element_t *) * ATTR_HASH_TABLE_SIZE);
  301.     current_regions = nextpos = NULL;
  302.     return 0;
  303. }
  304.  
  305. /*
  306.  * creates a data structure containing the list of attributes
  307.  * which occur at increasing offsets in the given file -- future
  308.  * region_identify() calls use the "current" data structure.
  309.  * returns 0 if success, -1 if it cannot open the file.
  310.  */
  311. int
  312. region_create(name)
  313.     char    *name;
  314. {
  315.     FILE    *fp;
  316.     AVList    *al;
  317.     region_t *prl, *rl, *lastrl;
  318.     Template *t;
  319.     char    temp[1024];
  320.  
  321.     current_regions = nextpos = NULL;
  322.     if ((fp = fopen(name, "r")) == NULL) return -1;
  323.     init_parse_template_file(fp);
  324.  
  325.     lastrl = NULL;
  326.     while ((t = parse_template()) != NULL) {
  327.         /* do insertion sort of list returned by parse_template using offsets */
  328.         if ((t->url != NULL) && (strlen(t->url) > 0)) {
  329.             rl = (region_t *)my_malloc(sizeof(region_t));
  330.             /* Darren Hardy's Voodo :-) */
  331.                         /* The SOIF looks like this:  @TTYPE { URL\n */
  332.                         /* t->offset points to the @ */
  333.                         /* rl->offset points to the space before URL */
  334.                         /* rl->length includes the entire URL */
  335.                         rl->offset = t->offset + strlen(t->template_type) + 3;
  336.                         rl->length = strlen(t->url) + 1;
  337.             rl->attributeid = attr_insert_name("url", 3);
  338.  
  339.             if ((lastrl != NULL) && (lastrl->offset <= rl->offset)) {    /* go forward */
  340.                 prl = lastrl;
  341.                 while (prl->next != NULL) {
  342.                     if (prl->next->offset > rl->offset) {
  343.                         rl->prev = prl;
  344.                         rl->next = prl->next;
  345.                         prl->next->prev = rl;
  346.                         prl->next = rl;
  347.                         lastrl = rl;
  348.                         break;
  349.                     }
  350.                     else prl = prl->next;
  351.                 }
  352.                 if (prl->next == NULL) {
  353.                     rl->next = NULL;
  354.                     rl->prev = prl;
  355.                     prl->next = rl;
  356.                     lastrl = rl;
  357.                 }
  358.             }
  359.             else {    /* must go backwards and find the right place to insert */
  360.                 prl = lastrl;
  361.                 while (prl != NULL) {
  362.                     if (prl->offset < rl->offset) {
  363.                         rl->prev = prl;
  364.                         rl->next = prl->next;
  365.                         if (prl->next != NULL)
  366.                             prl->next->prev = rl;
  367.                         prl->next = rl;
  368.                         lastrl = rl;
  369.                         break;
  370.                     }
  371.                     else prl = prl->prev;
  372.                 }
  373.                 if (prl == NULL) {
  374.                     rl->next = current_regions;
  375.                     if (current_regions != NULL) current_regions->prev = rl;
  376.                     rl->prev = NULL;
  377.                     current_regions = rl;
  378.                     lastrl = rl;
  379.                 }
  380.             }
  381.  
  382. #if    0
  383.             printf("region url=[%d,%d]\n", rl->offset, rl->offset+rl->length);
  384. #endif    /*0*/
  385.         }
  386.  
  387.         al = t->list;
  388.         while(al != NULL) {
  389.             rl = (region_t *)my_malloc(sizeof(region_t));
  390.             rl->offset = al->data->offset;
  391.             rl->length = al->data->vsize;
  392.             attr_extract(temp, al->data->attribute);
  393.             rl->attributeid = attr_insert_name(temp, strlen(temp));
  394.  
  395.             if ((lastrl != NULL) && (lastrl->offset <= rl->offset)) {    /* go forward */
  396.                 prl = lastrl;
  397.                 while (prl->next != NULL) {
  398.                     if (prl->next->offset > rl->offset) {
  399.                         rl->prev = prl;
  400.                         rl->next = prl->next;
  401.                         prl->next->prev = rl;
  402.                         prl->next = rl;
  403.                         lastrl = rl;
  404.                         break;
  405.                     }
  406.                     else prl = prl->next;
  407.                 }
  408.                 if (prl->next == NULL) {
  409.                     rl->next = NULL;
  410.                     rl->prev = prl;
  411.                     prl->next = rl;
  412.                     lastrl = rl;
  413.                 }
  414.             }
  415.             else {    /* must go backwards and find the right place to insert */
  416.                 prl = lastrl;
  417.                 while (prl != NULL) {
  418.                     if (prl->offset < rl->offset) {
  419.                         rl->prev = prl;
  420.                         rl->next = prl->next;
  421.                         if (prl->next != NULL)
  422.                             prl->next->prev = rl;
  423.                         prl->next = rl;
  424.                         lastrl = rl;
  425.                         break;
  426.                     }
  427.                     else prl = prl->prev;
  428.                 }
  429.                 if (prl == NULL) {
  430.                     rl->next = current_regions;
  431.                     if (current_regions != NULL) current_regions->prev = rl;
  432.                     rl->prev = NULL;
  433.                     current_regions = rl;
  434.                     lastrl = rl;
  435.                 }
  436.             }
  437.  
  438. #if    0
  439.             printf("region %s=[%d,%d]\n", al->data->attribute, rl->offset, rl->offset+rl->length);
  440. #endif    /*0*/
  441.             al = al->next;
  442.         }
  443.         free_template(t);
  444.     }
  445.     finish_parse_template();
  446.     nextpos = current_regions;
  447.     fclose(fp);
  448.     return 0;
  449. }
  450.  
  451. /*
  452.  * frees the data structure created for the current file above.
  453.  * returns 0.
  454.  */
  455. int
  456. region_destroy()
  457. {
  458.     region_t *rl = current_regions, *trl;
  459.  
  460.     while (rl != NULL) {
  461.         trl = rl;
  462.         rl = rl->next;
  463.         free(trl, sizeof(region_t));
  464.     }
  465.     current_regions = nextpos = NULL;
  466.     return 0;
  467. }
  468.  
  469. /*
  470.  * returns attribute number [1..num_attr] which covers (inclusive)
  471.  * the region * [offset, offset+len] in the "current" file, 0 if none.
  472.  * called during indexing after region_create, and search after
  473.  * attr_load_names. Do not need sophisticated interval trees here!
  474.  */
  475. int
  476. region_identify(offset, len)
  477.     int    offset, len;
  478. {
  479.     region_t *rl;
  480.  
  481.     if (nextpos == NULL) nextpos = current_regions;
  482.     rl = nextpos;
  483.     while (rl!=NULL) {
  484.         if (rl->offset > offset + len)
  485.             goto backwards;            /* definitely before: can be earlier region OR hole */
  486.         else if ((rl->offset <= offset) && (rl->offset + rl->length >= offset + len))
  487.             return rl->attributeid;        /* definitely within */
  488.         else if (rl->offset + rl->length < offset)
  489.             nextpos = rl = rl->next;    /* definitely after: later region */
  490.         else return 0;                /* overlapping: error */
  491.     }
  492.     return 0;                    /* reached end of file */
  493.  
  494. backwards:
  495.     while (rl!=NULL) {
  496.         if (rl->offset > offset + len)
  497.             nextpos = rl = rl->prev;    /* definitely before: earlier region */
  498.         else if ((rl->offset <= offset) && (rl->length + rl->length >= offset + len))
  499.             return rl->attributeid;        /* definitely within */
  500.         else if (rl->offset + rl->length < offset)
  501.             return 0;            /* hole */
  502.         else return 0;                /* overlapping: error */
  503.     }
  504.     return 0;                    /* reached end of file */
  505. }
  506.  
  507. #else    /*STRUCTURED_QUERIES*/
  508.  
  509. int attr_num = 0;
  510.  
  511. char *attr_id_to_name(id)
  512.     int    id;
  513. {
  514.     return NULL;
  515. }
  516.  
  517. int attr_name_to_id(name)
  518.     char    *name;
  519. {
  520.     return 0;
  521. }
  522.  
  523. int attr_dump_names(name)
  524.     char    *name;
  525. {
  526.     return 0;
  527. }
  528.  
  529. int attr_load_names(name)
  530.     char    *name;
  531. {
  532.     return 0;
  533. }
  534.  
  535. int attr_free_table()
  536. {
  537.     return 0;
  538. }
  539.  
  540. int region_initialize()
  541. {
  542.     return 0;
  543. }
  544.  
  545. int region_desrtroy()
  546. {
  547.     return 0;
  548. }
  549.  
  550. int region_create(name)
  551.     char    *name;
  552. {
  553.     return 0;
  554. }
  555.  
  556. int region_destroy()
  557. {
  558.     return 0;
  559. }
  560.  
  561. int region_identify(offset, len)
  562.     int    offset, len;
  563. {
  564.     return 0;
  565. }
  566. #endif    /*STRUCTURED_QUERIES*/
  567.